package com.fr.lintcode;

import java.util.List;

public class Q1676 {

	/**
	 * @param n:      The total number of stones.
	 * @param m:      The total number of stones you can remove.
	 * @param target: The distance from the end to the starting point.
	 * @param d:      The array that the distance from the i rock to the starting
	 *                point is d[i].
	 * @return: Return the maximum value of the shortest jump distance.
	 */
	// 二分 区间dp，但是看题目给的数据量级，dp是肯定不行的
	public int getDistance(int n, int m, int target, List<Integer> d) {
		// Write your code here.
		if (n == 0) {
			return target;
		}
		int start = 0, end = target;
		d.add(target);
		while (start + 1 < end) {
			int mid = start + (end - start) / 2;
			if (isValid(n, m, target, d, mid)) {
				start = mid;
			}else {
				end = mid;
			}
		}
		if (isValid(n, m, target, d, end)) {
			return end;
		}
		return start;
	}
    //如果最小值为gap，那么需要移除count个石头
	boolean isValid(int n, int m, int target, List<Integer> d, int gap) {
		int count = 0, lastPos = 0;
		for (int i = 0; i <= n; ++i) {
			if (d.get(i) - lastPos < gap) {
				count++;
			}else {
				lastPos = d.get(i);
			}
				
		}

		return count <= m;
	}

}
